//
// Created by daiyizheng on 2022/3/27.
//
#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//dfs返回root为根节点的子树的最大贡献值
int maxSum = INT_MIN;
int maxGain(TreeNode* root){
    if (root== nullptr)return 0;

    int left  = max(maxGain(root->left), 0);
    int right = max(maxGain(root->right), 0);

    maxSum = max(maxSum,left+right+root->val);

    return max(root->val+left , root->val+right);
}
int maxPathSum(TreeNode* root) {
    maxGain(root);
    return maxSum;
}
